package gold.digger;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC395 {
    public long startExecuteTime = System.currentTimeMillis();

//    Input:
//    s = "ababbc", k = 2
//
//    Output:
//            5

//    The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

    public int longestSubstring(String s, int k) {
        Map<String, Integer> dict = new HashMap<>();
        return longestSubstringRecur(s, k, 0, s.length() - 1, dict);
    }

    public int longestSubstringRecur(String s, int k, int start, int end, Map<String, Integer> dict) {
        if (null == s || s.length() <= 0 || start > end) {
            return 0;
        }

        if (dict.containsKey(s.substring(start, end + 1))) {
            return dict.get(s.substring(start, end + 1));
        }

        int[] arr = new int[26];
        for (int i = start; i <= end; i++) {
            arr[s.charAt(i) - 'a']++;
        }

        for (int i = start; i <= end; i++) {
            if (arr[s.charAt(i) - 'a'] < k) {
                int left = longestSubstringRecur(s, k, start, i - 1, dict);
                int right = longestSubstringRecur(s, k, i + 1, end, dict);

                if (left > right) {
                    dict.put(s.substring(start, i), left);
                    return left;
                } else {
                    dict.put(s.substring(i + 1, end + 1), right);
                    return right;
                }
            }
        }

        dict.put(s.substring(start, end + 1), end - start + 1);
        return end - start + 1;
    }


    public static void main(String[] args) throws Exception {
        LC395 an = new LC395();
        String test = "ababbc";
        System.out.println(an.longestSubstring(test, 2));

        System.out.println("\nanswer total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
